﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace D
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
          //  label1.Text = "Kết Quả";
            this.Lis = new List<int>();
           }


        List<int> lis;

        public List<int> Lis
        {
            get { return lis; }
            set { lis = value; }
        }
        //doi 1 so ra nhi phan
        private string conv(int a)
        {
            string s=null;
            while (a > 0)
            {
                s = (a % 2).ToString()+s;
                a = a / 2;

            }
            return s;
        }
     //tinh a^b mod c
       private int mumod(int a, int b, int c)
        {   string s=null;
            int y=1;
            if (b==0) return 1; else s = conv(b);
            if (s[s.Length - 1] == '1') y = a; 
            int k = a;
            for (int i = s.Length-2; i >= 0; i--)
            {   
                k = (k * k)%c;
                if (s[i] == '1') y = k*y % c;
               
            }
            return y;
        }
       private bool ktnt1(int a)
       {
           bool kt = true;
           if (a < 2) kt=false;
           else 
               for (int i=2;i<a;i++)
                   if (a % i == 0) { kt = false; break; }
           return kt;
       }
        //Miller
       int j = 0;
       String m = null;
        private void ktnt(int n, int b)
       {
         //  string m ;
          
            int y = (n - 1) / 2;
            bool kt = true;
            while (kt==true)
            {
                if ((mumod(b, y, n) != 1) && (mumod(b, y, n) != n - 1)) { m = m + "y= " + y.ToString() + "; " +"b^y (mod n)= "+ mumod(b, y, n).ToString() + "\r\n"; kt = false;
                j--;
                    //label1.Text = "Không là số nguyên tố"; 
                }
                else
                    if ((mumod(b, y, n) == n - 1) || ((mumod(b, y, n) == 1) && (y % 2 == 1)))
                    {
                        if ((mumod(b, y, n) == n - 1)) m = m + "y= " + y.ToString() + "; " + "b^y (mod n)= " + "-1" + "\r\n";
                        else m = m + "y= " + y.ToString() + "; " + "b^y (mod n)= " + mumod(b, y, n).ToString() + "\r\n"; 
                        kt = false;
                        j++;
                        //label1.Text = "Là số Nguyên tố";
                    }
                    else
                        if ((mumod(b, y, n) == 1) && (y % 2 == 0)) { m = m + "y= " + y.ToString() + "; " + "b^y (mod n)= " + mumod(b, y, n).ToString() + "\r\n"; y = y / 2; kt = true;  } 
                    }
            textBox3.Text = m;
        }

        private void button1_Click(object sender, EventArgs e)
        {
            if ((textBox1.Text == null) || (textBox2.Text == null))
            {
                MessageBox.Show("Không được để trống");

            } 
            int a = Convert.ToInt32(textBox1.Text);
          //  int b = Convert.ToInt32(textBox2.Text);
            for (int i = 1; i < a; i++)
            {// string m=null;
            m = m + "b= " + i.ToString() + "; " +"\r\n"; 
                   textBox3.Text = m;

            //    textBox3.Text = "b=" + i.ToString();
              
                ktnt(a, i);
            } 
            if (j > 0.75 * a) label1.Text = "số "+a+ " là số Nguyên tố";
            else label1.Text = " Số "+ a +" ko Là số Nguyên tố";
        }
    
        
        //de quy FM
        int i;
        private string dqfm(int a)
        {
            string m = null;
            if ((int)Math.Sqrt(a) * (int)Math.Sqrt(a) == a)// kt so chinh phuong
            {
                //return a.ToString() + " = " + Math.Sqrt(a).ToString() + "x" + Math.Sqrt(a).ToString();
                this.lis.Add((int)Math.Sqrt(a));
                this.Lis.Add((int)Math.Sqrt(a));
            }
            else
            {
                int h = 0;
                for (i = (int)Math.Sqrt(a) + 1; i <= (a + 1) / 2; i++)
                {
                    //  m = m + i.ToString() + "^2 - " + a.ToString() + " = " + (i * i).ToString() + " - " + a.ToString() + " = " + (i * i - a).ToString() + "\r\n";
                    int tam = i * i - a;
                     h = (int)Math.Sqrt(tam);
                    if (h * h == tam) //dung khi xuat hien so chinh phuong
                    {
                        break;
                        //m = m+tam.ToString() + " = " + h.ToString() + "^2";

                        //   label1.Text = a.ToString() + " = (" + i.ToString() + " + " + h.ToString() + ")(" + i.ToString() + " - " + h.ToString() + ")" + " = " + (i + h).ToString() + "x" + (i - h).ToString();


                        // if (Math.Sqrt(i + h) * Math.Sqrt(i + h) == i + h) { 

                        //  } 
                    }

                }
                int temp1 = i + h;
                int temp2 = i - h;
                if (ktnt1(temp1) == true || temp1 == 1) this.Lis.Add(temp1);
                else dqfm(temp1);
                if (ktnt1(temp2) == true || temp2 == 1) this.Lis.Add(temp2);
                else dqfm(temp2);
            }
            textBox3.Text = m; 
            return m;
      
            //
        }
        void show(List<int> l)
        {   
            string s = String.Empty;
            foreach (int i in l)
            {
                
                s+=i.ToString();
                s += "  ";
                
            }
            label1.Text = s;
        }
        //Fermat
        private void button2_Click(object sender, EventArgs e)
        {     int a=Convert.ToInt32(textBox1.Text);
        label1.Text = null;
        lis.Clear();
    /*    if (ktnt1(i + h) == false)
        {
            dqfm(i + h);
        }
        if (ktnt1(i - h) == false)
        {
            dqfm(i - h);

        }
        label1.Text = a.ToString() + " = (" + i.ToString() + " + " + h.ToString() + ")(" + i.ToString() + " - " + h.ToString() + ")" + " = " + (i + h).ToString() + "x" + (i - h).ToString();
*/textBox3.Text = dqfm(a);
  show(this.Lis);
           
        }
        //uoc chung lon nhat cua 2 so lon
        private int GCD(int a, int b)
        {
            int r = a % b;
            while (r != 0)
            {   
                a = b;
                b = r;
                r = a % b;
            }
            return b;
        }
        //Rho
        private void button3_Click(object sender, EventArgs e)
        { 
            if ((textBox1.Text == null))
            {
                MessageBox.Show("Không được để trống");
                textBox1.Focus();

            }
            string m = null;
            int a = Convert.ToInt32(textBox1.Text);
            //tien hanh
            Random x = new Random();
            int r=x.Next((int)Math.Sqrt(a),a);
            label3.Text = "Cơ sở ngẫu nhiên";
            textBox2.Text = r.ToString();
            m = "r1 = " + r.ToString() + "( mod" + a.ToString() + " )"+"\r\n";
            int i = 1;
            int tam=r%a;
            while (GCD(tam - 1, a) == 1)
            {
                i += 1;
                tam = mumod(tam, i, a);
                m = m + "r" + i.ToString() + " = " + "r" + (i - 1).ToString() + "^2= " + tam.ToString() + "(mod" + a.ToString() + ")" + "   " + "gcd(r" + i.ToString() + "-1,n)=" + GCD(tam - 1, a)+"\r\n";

            }
            textBox3.Text = m;
            label1.Text = GCD(tam - 1, a).ToString();
            

        }
        //monte carlo
        private void button4_Click(object sender, EventArgs e)
        {
            int a = Convert.ToInt32(textBox1.Text);
            if (ktnt1(a)) label1.Text = a.ToString()+" = 1 x "+a.ToString();//ktra co la nt
            else
            {
                string s = a.ToString() + " = ";
                while (a > 1)
                {
                    int i = 2;
                    while (i <= a)
                    {
                        if ((a % i == 0) && (ktnt1(i)))
                            if (a / i == 1) { s = s + i; a = a / i; }//phan tich tiep a/i
                            else { s = s + i + " x "; a = a / i; }
                        else i = i + 1;
                    }
                }
                label1.Text = s;
            }
       
        }

        private void button5_Click(object sender, EventArgs e)
        {
            int a = Convert.ToInt32(textBox1.Text);
            if (ktnt1(a)) label1.Text = "Là Số Nguyên Tố"; else label1.Text = "Không là số nguyên tố";
        }

        private void Form1_Load(object sender, EventArgs e)
        {

        }

        private void textBox3_TextChanged(object sender, EventArgs e)
        {

        }

        private void groupBox1_Enter(object sender, EventArgs e)
        {

        }
       

    }
}

